4.1. Das Gauß'sche Eliminationsverfahren

Im Mathematikunterricht lernten wir, lineare Gleichungssysteme mit mehreren Unbekannten zu lösen. Allerdings beschränkten wir uns auf sogenannte 2x2-Systeme, d.h. Systeme mit zwei Gleichungen und zwei Unbekannten.

Solche Systeme konnten entweder keine, eine oder unendlich viele Lösungen haben. Der Einfachheit halber wollen wir uns im Folgenden mit den eindeutig lösbaren Systemen beschäftigen.

Wir haben bisher zwei Lösungsverfahren kennen gelernt: Das Einsetzverfahren und das Additionsverfahren.

Das Einsetzverfahren ist vielleicht leichter zu verstehen, aber leider ungeeignet, um lineare Gleichungsysteme mit mehr als 2 Gleichungen und 2 Unbekannten zu lösen. Die nötigen Rechnungen werden im Allgemeinen zu aufwendig. Deshalb wollen wir uns im Folgenden auf das Additionsverfahren konzentrieren.

Beim Additionsverfahren werden die einzelnen Unbekannten der Reihe nach eliminiert, bis nur noch eine übrig ist. Man nennt es deswegen auch das Eliminationsverfahren.

Beispiel: Lösung eines 3x3-Systems mit dem Additionsverfahren

Um die ersten Summanden in den Zeilen II und III zu eliminieren, müssen wir Additionen mit geeigneten Vorfaktoren durchführen:

Die Additionen  und  bringen uns ans Ziel.

Wir finden die gesuchten Vorfaktoren, indem wir jeweils den Koeffizienten von x1 der II. bzw. III. Gleichung durch den Koeffizienten von der I. Gleichung dividieren und mit einem Minuszeichen versehen.

Bemerkung: In unserem Beispiel ist glücklicherweise der erste Koeffizient der ersten Gleichung von Null verschieden, da sonst die geforderte Division nicht möglich wäre. Wir müssten die Gleichungen solange umsortieren, bis wir eine geeignete gefunden haben. Die Suche nach einem solchen von Null verschiedenen Koeffizienten heißt Pivotsuche, der Koeffizient selbst Pivotelement. Da wir nur eindeutig lösbare Systeme betrachten, können wir davon ausgehen, dass mindestens eine der drei Gleichungen die Bedingung erfüllt.

Um die Unbekannte  bestimmen zu können, müssen wir noch die Variable  in III' eliminieren.

Dies geschieht mit der Addition :

Damit hat unser Gleichungssystem eine besondere Form erhalten, die man obere Dreiecksform nennt. Aus ihr lässt sich die Lösung des Systems leicht berechnen:

Aus Zeile III" läßt sich sofort  ablesen. Setzen wir den gefundenen Wert in II' ein, so erhalten wir . Mit den so gefundenen Werten und der Gleichung I lässt sich auch  schnell berechnen.
 
 
 

Das Ziel eines Lösungsalgorithmus muss es also sein, durch fortgesetzte Addition der einzelnen Zeilen mit geeigneten Vorfaktoren das Gleichungssystem in die Dreiecksform überzuführen. Dabei muss aber immer darauf geachtet werden, dass die Koeffizienten, die zur Berechnung der Vorfaktoren herangezogen werden, von Null verschieden sind, sonst muss eine Pivotsuche durchgeführt werden. Der beschriebene Algorithmus ist nach dem berühmten Mathematiker Carl Friedrich Gauß benannt.

Carl Friedrich Gauß (1777 - 1855)

Die Umsetzung in ein PASCAL-Programm führen wir zunächst für ein 3x3-System durch. Dieses Programm lässt sich dann leicht auf n x n - Systeme verallgemeinern.

Außerdem gehen wir davon aus, dass eine Pivotsuche nicht nötig ist, sondern dass alle nötigen Koeffizienten immer von Null verschieden sind. Dies ist eine sehr starke und nicht haltbare Einschränkung, hilft uns jedoch sehr bei der Erstellung eines ersten Programms, da es den Algorithmus stark vereinfacht.

Musterlösung (einfache Version):

 1: program Gauss_Algorithmus; { Einfache Version }
 2: uses CRT;
 3: const
 4:    Rang=3;
 5: var
 6:    Koeff: array[1..Rang,1..Rang] of Real;
 7:    Erg: array[1..Rang] of Real;
 8:    x,y:Integer;
 9:    Faktor:Real;
10:
11: procedure Koeffizienteneingabe;
12: var
13:     i,j:Integer;
14: begin
15:     ClrScr;
16:    for i:=1 to rang do
17:    begin
18:       Writeln('Zeilenweise Koeffizienteneingabe');
19:    for j:=1 to rang do
20:    begin
21:          Write('a(',i,',',j,'): ');
22:          Readln(koeff[i,j]);
23:    end;
24:       Writeln('Ergebniseingabe: ');
25:       Write('b(',i,'): ');
26:       Readln(Erg[i]);
27:    end;
28: end;
29:
30: procedure Koeffizientenausgabe;
31: var
32:    i,j:Integer;
33: begin
34:    Writeln;
35:    Writeln('Koeffizientenausgabe');
36:    Writeln;
37:    for i:=1 to rang do
38:    begin
39:    for j:=1 to rang do
40:    begin
41:    if koeff[i,j]<>0 then
42:             Write(koeff[i,j]:8:4,' ':6)
43:    else
44:             Write(' ':8,' ':6);
45:    end;
46:       Write('=>');
47:       Writeln(Erg[i]:8:4);
48:    end;
49:    Writeln;
50: end;
51:
52: procedure Zeilenaddition(Nr1,Nr2:integer;Faktor:Real);
53: var
54:    i:Integer;
55: begin
56:    for i:=1 to rang do
57:       Koeff[Nr2,i]:=Koeff[Nr2,i]+Faktor*Koeff[Nr1,i];
58:    Erg[Nr2]:=Erg[Nr2]+Faktor*Erg[Nr1];
59: end;
60:
61: begin
62:    KoeffizientenEingabe;
63:    for x:=1 to rang-1 do { Elimination aller Variablen bis auf }
64:    begin { die letzte }
65:    for y:=x+1 to rang do
66:    begin { Elimination der x-ten Variable in }
67:             { allen verbleibenden Zeilen }
68:          Faktor:=-Koeff[y,x]/Koeff[x,x];
69:          Zeilenaddition(x,y,Faktor);
70:    end;
71:       Koeffizientenausgabe;
72:    if x=Rang-1 then
73:          Write('Gauß-Algorithmus beendet, Dreiecksform erreicht!')
74:    else
75:          Write('Return...');
76:       Readln;
77:    end;
78: end.

Dieser Koeffizient selbst heißt Pivotelement, die Suche wird als Pivotsuche bezeichnet. Da wir nur eindeutig lösbare Systeme betrachten, können wir davon ausgehen, dass mindestens eine der drei Gleichungen die Bedingung erfüllt.

Erhalten wir also bei der Durchführung des Gauß’schen Algorithmus einen Koeffizienten mit dem Wert Null, so vertauschen wir einfach die entsprechende Zeile mit einer anderen, in der der Koeffizient ungleich Null ist.

Um dies in unserem Programm berücksichtigen zu können, ergänzen wir es um eine Prozedur Pivotsuche, die das Gleichungssystem für eine bestimmte Spalte nach Koeffizienten ungleich Null durchsucht und dann gegebenenfalls die entsprechenden Zeilen vertauscht.

Die entsprechende Prozedur lautet:

procedure Pivotsuche(Spalte:Integer);
var
   i:Integer;
begin
   i:=Spalte;
   while Koeff[i,Spalte]=0 do
   begin
      i:=i+1;
     if i>Rang then
     begin
         Writeln;
         Writeln('Das ',Rang,'x',Rang,'-System ist nicht eindeutig lösbar!');
         Readln;
         halt(1); { Programmabbruch }
     end;
   end;
   Zeilentausch(i,Spalte);
end;

Musterlösung (erweiterte Version mit Pivotsuche):

  1: program Gauss_Algorithmus; { erweiterte Version }
  2: uses CRT;
  3: const
  4:    Rang=3;
  5: var
  6:    Koeff: array[1..Rang,1..Rang] of Real;
  7:    Erg: array[1..Rang] of Real;
  8:    x,y:Integer;
  9:    Faktor:Real;
 10:
 11: procedure Koeffizienteneingabe;
 12: var
 13:    i,j:Integer;
 14: begin
 15:  ClrScr;
 16:    for i:=1 to rang do
 17:    begin
 18:       Writeln('Koeffizienteneingabe');
 19:       for j:=1 to rang do
 20:       begin
 21:       Write('a(',i,',',j,'): ');
 22:       Readln(koeff[i,j]);
 23:       end;
 24:       Writeln('Ergebniseingabe: ');
 25:       Write('b(',i,'): ');
 26:       Readln(Erg[i]);
 27:    end;
 28: end;
 29:
 30: procedure Koeffizientenausgabe;
 31: var
 32:    i,j:Integer;
 33: begin
 34:    Writeln;
 35:    Writeln('Koeffizientenausgabe');
 36:    Writeln;
 37:    for i:=1 to rang do
 38:    begin
 39:       for j:=1 to rang do
 40:       begin
 41:       if koeff[i,j]<>0 then
 42:       Write(koeff[i,j]:8:4,' ':6)
 43:       else
 44:       Write(' ':8,' ':6);
 45:       end;
 46:       Write('=>');
 47:       Writeln(Erg[i]:8:4);
 48:    end;
 49:    Writeln;
 50: end;
 51:
 52: procedure Zeilentausch(Nr1,Nr2:Integer);
 53: var
 54:    i:Integer;
 55:    h:real;
 56: begin
 57:    if Nr1<>Nr2 then
 58:    begin
 59:       for i:=1 to Rang do
 60:       begin
 61:       h:=Koeff[Nr2,i];
 62:       Koeff[Nr2,i]:=Koeff[Nr1,i];
 63:       Koeff[Nr1,i]:=h;
 64:       end;
 65:       h:=Erg[Nr2];
 66:       Erg[Nr2]:=Erg[Nr1];
 67:       Erg[Nr1]:=h;
 68:    end;
 69: end;
 70:
 71: procedure Pivotsuche(Spalte:Integer);
 72: var
 73:    i:Integer;
 74: begin
 75:    i:=Spalte;
 76:    while Koeff[i,Spalte]=0 do
 77:    begin
 78:       i:=i+1;
 79:       if i>Rang then
 80:       begin
 81:       Writeln;
 82:       Writeln('Das ',Rang,'x',Rang,'-System ist nicht eindeutig lösbar!');
 83:       Readln;
 84:       halt(1); { Programmabbruch }
 85:       end;
 86:    end;
 87:    Zeilentausch(i,Spalte);
 88: end;
 89:
 90: procedure Zeilenaddition(Nr1,Nr2:integer; Faktor:Real);
 91: var
 92:    i:Integer;
 93: begin
 94:    for i:=1 to Rang do
 95:    begin
 96:       Koeff[Nr2,i]:=Koeff[Nr2,i]+Faktor*Koeff[Nr1,i];
 97:    end;
 98:    Erg[Nr2]:=Erg[Nr2]+Faktor*Erg[Nr1];
 99: end;
100:
101: begin
102:   KoeffizientenEingabe;
103:   for x:=1 to Rang-1 do
104:   begin
105:     Pivotsuche(x);
106:     for y:=x+1 to Rang do
107:     begin
108:        Faktor:=-Koeff[y,x]/Koeff[x,x];
109:        Zeilenaddition(x,y,Faktor);
110:     end;
111:     KoeffizientenAusgabe;
112:     if x=Rang-1 then
113:        Writeln('Gauß-Algorithmus beendet, Dreiecksform erreicht!')
114:     else
115:        Writeln('Return drücken...');
116:     Readln;
117:   end;
118: end.

Das Beispiel

macht eine Pivotsuche erforderlich. Schon beim ersten Schritt müsste durch den Koeffizienten  der ersten Gleichung dividiert werden. In der vorliegenden Form ist dieser gleich Null und würde somit zu einem Programmabsturz führen. Abhilfe schafft z.B. das Vertauschen der Zeilen I und II.

Die erweiterte Version unseres Programmes führt dazu eine Pivotsuche und eine Zeilenvertauschung durch und löst das Gleichungssystem. Die einfache Version kann diese Beispiel nicht lösen (Ausprobieren!).

Programmablauf nach Eingabe der Koeffizienten:

Soll das Programm nicht nur die Dreiecksform des Gleichungssystems anzeigen, sondern auch die Lösung selbst produzieren, so kann die folgende Prozedur verwendet werden. Sie muss mittels Loesesystem; aufgerufen werden. Der Aufruf erfolgt als letzte Anweisung vor dem alles beendenden end. Die Prozedur kann in beiden Programmen verwendet werden.

Musterlösung:

 1': procedure LoeseSystem;
 2': var
 3':    Lsg:array[1..Rang] of Real;
 4':    i,j:Integer;
 5': begin
 6':    for i:=Rang downto 1 do
 7':    begin
 8':       lsg[i]:=erg[i];
 9':       for j:=i+1 to rang do
10':          lsg[i]:=lsg[i]-Koeff[i,j]*lsg[j];
11':       lsg[i]:=lsg[i]/Koeff[i,i];
12':    end;
13':    Writeln('Lösung des Systems: ');
14':    Writeln;
15':    for i:=1 to rang do
16':        Writeln('x[',i,'] = ',lsg[i]:12:6);
17': end;

Als weiteres Beispiel lösen wir nun ein 4x4-System. In beiden Musterprogrammen wurde die Größe des Systems lediglich durch die Konstante Rang festgelegt. Dies kommt uns nun beim Programmieren zugute. Ohne großen Aufwand erhalten wir ein Programm zur Lösung eines 4x4-Systems, indem wir lediglich die Konstante Rang auf den Wert 4 setzen. Rang kann beliebig erhöht werden und ist nur durch die Kapazität des verwendeten Rechners beschränkt.

Beispiel:

Nach Eingabe der Koeffizienten zeigt das so erweiterte Programm nicht nur das transformierte Gleichungssystem, sondern auch die tatsächliche Lösung an:

 

Koeffizientenausgabe  -> 1.0000 ->  2.0000 ->   4.0000 ->  -3.0000 =>   43.0000  ->        ->  4.0000 ->  -9.0000 ->  11.0000 =>  -54.0000  ->        ->         -> -14.0000 ->   4.0000 => -102.0000  ->        -> 19.0000 ->  30.0000 -> -21.0000 =>  326.0000  Koeffizientenausgabe  -> 1.0000 ->  2.0000 ->   4.0000 ->  -3.0000 =>   43.0000  ->        ->  4.0000 ->  -9.0000 ->  11.0000 =>  -54.0000  ->        ->         -> -14.0000 ->   4.0000 => -102.0000  ->        ->         ->  72.7500 -> -73.2500 =>  582.5000  Koeffizientenausgabe  -> 1.0000 ->  2.0000 ->   4.0000 ->  -3.0000 =>   43.0000  ->        ->  4.0000 ->  -9.0000 ->  11.0000 =>  -54.0000  ->        ->         -> -14.0000 ->   4.0000 => -102.0000  ->        ->         ->          -> -52.4643 =>   52.4643  Gauß-Algorithmus beendet, Dreiecksform erreicht!  Lösung des Systems:  x[1] =  2.000000  x[2] =  5.000000  x[3] =  7.000000  x[4] = -1.000000

In diesem Kapitel entwickelten wir ein Programm zur numerischen Lösung von linearen Gleichungssystemen. Ein solches Programm ist für Mathematiker oder Ingenieure, aber auch für Schüler und Studenten ein wichtiges Hilfsmittel, da es aufwendige Rechnungen übernehmen kann.

Daher gibt es auf dem Software-Markt eine ganze Reihe von diesen Programmen.

Meistens können sie aber nicht nur lineare Gleichungssysteme lösen, sondern besitzen viel weiterreichende Fähigkeiten und können zur Lösung unterschiedlichster Probleme eingesetzt werden .

Für den Mathematikunterricht sind sogenannte Computeralgebrasysteme wie DERIVE, MuPad, MAPLE oder MATHEMATICA von Interesse. Sie erlauben uns die Lösung vielfältiger Probleme aus dem Bereich der Mathematik.

So können sie bei der Behandlung von linearen Gleichungssystemen nicht nur die numerischen Lösungen ermitteln, sondern sogar formal exakt berechnen. Dies ist vor allem dann erforderlich, wenn in einem Gleichungsssystem nicht nur Variablen, sondern noch Parameter enthalten sind.

Beispiel: Zu lösen ist das folgende Gleichungssystem, das außer den Variablen x und y noch den Parameter a enthält, wobei a eine reelle Zahl sein soll:

Zur Lösung beginnen wir mit der Subtrakion II - I. Daraus folgt:

Aus II' kann, unter der Voraussetzung, direkt x berechnet werden:

Mit der so bestimmten Lösung für x können wir durch Einsetzen in I auch y berechnen:

Wir erhalten also als Lösung unseres Gleichungssystems:

, 

Nach Eingabe der beiden Gleichungen in der Form [a x + y = 0.5 , x + y = 1]

berechnet DERIVE mittels des Befehls SOLVE SYSTEM direkt die Lösung unseres Gleichungssystems:

Abb.: Ausgabebildschirm des Compteralgebrasystems DERIVE zur Lösung des obigen Beispieles

Aufgaben:

1. Gegeben sind die folgenden linearen Gleichungssysteme:
    
   2x2 - System: 
   3x3 - System:
    
   1.  Löse die folgenden linearen Gleichungssysteme mit dem Einsetzverfahren mittels Bleistift und Papier. Was fällt dir auf ?
   2.  Löse die beiden Gleichungssystem durch Transformation auf Dreiecksform ebenfalls mittels Bleistift und Papier.

   
   Hinweis: Falls die Aufgabe 3 des Kapitels 3.1.2 ausführlich bearbeitet wurde, so kann das dort erstellte Programm sehr hilfreich benutzt werden.
    

2. Löse mit einem PASCAL-Programm die folgenden 3x3-Systeme.
   1. 
   2. 
    
3. Ein lineares Gleichungssystem mit betragsmäßig sehr unterschiedlich großen Koeffizienten ist nicht so einfach zu lösen, da hier kleine Rundungsfehler schon zu großen Ungenauigkeiten des Ergebnisses führen. Man sagt, es neigt zu numerischer Instabilität.
   Zur Lösung solcher linearen Gleichungssysteme ist es notwendig, die Pivotsuche abzuändern. Eine solche verbesserte Pivotsuche ist in folgender Prozedur dargestellt:
    
    1': procedure Pivotsuche(x:Integer);
    2': var
    3': i,MaxIndex:Integer;
    4': begin
    5':   MaxIndex:=x;
    6':   for i:=x to rang do
    7':   begin
    8':      if Abs(Koeff[i,x])>Abs(Koeff[Maxindex,x]) then MaxIndex:=i;
    9':   end;
   10':    if Koeff[MaxIndex,x]=0 then
   11':    begin
   12':      GotoXY(2,24);
   13':      Write('Das ',Rang,'x',Rang,'-System ist nicht eindeutig lösbar!');
   14':      halt(1);
   15':    end;
   16':    Zeilentausch(x,MaxIndex);
   17': end;
    
   1. Erkläre kurz den Aufbau und Ablauf der Prozedur.
   2. Worin liegt der Unterschied zur einfachen Pivotsuche?
   3. Ersetze die im Musterprogramm verwendete Prozedur durch die neue Pivotsuche und teste ihre Wirkung an dem folgenden Gleichungssystem: Vergleiche die Ergebnisse des Lösungsprogrammes mit der alten Pivotsuche mit den Ergebnissen einer Version der neuen Pivotsuche.

      Zum Vergleich: Die exakten Lösungen des Programms sind:

      .